package uestc.lj.midPromotion.dfs;

/**
 * 二维数组matrix，其中每个数都是正数，要求从左上角走到右下角。每一步只能向右或向下，沿途经过的数字要累加。
 * 最后返回最小的路径和
 *
 * @Author:Crazlee
 * @Date:2021/11/30
 */
public class Code04_MinPathSum {
	public static int minPathSum1(int[][] arr) {
		if (arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0) {
			return 0;
		}
		int row = arr.length;
		int col = arr[0].length;
		int[][] dp = new int[row][col];
		dp[0][0] = arr[0][0];
		for (int i = 1; i < row; i++) {
			dp[i][0] = dp[i - 1][0] + arr[i][0];
		}
		for (int i = 1; i < col; i++) {
			dp[0][i] = dp[0][i - 1] + arr[0][i];
		}
		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
			}
		}
		return dp[row - 1][col - 1];
	}

	public static int minPathSum2(int[][] m) {
		if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
			return 0;
		}
		int more = Math.max(m.length, m[0].length);
		int less = Math.min(m.length, m[0].length);

		boolean rowmore = more == m.length;
		int[] arr = new int[less];
		arr[0] = m[0][0];
		for (int i = 1; i < less; i++) {
			arr[i] = arr[i - 1] + (rowmore ? m[0][i] : m[i][0]);
		}
		for (int i = 1; i < more; i++) {
			arr[0] = arr[0] + (rowmore ? m[i][0] : m[0][i]);
			for (int j = 1; j < less; j++) {
				arr[j] = Math.min(arr[j - 1], arr[j])
						+ (rowmore ? m[i][j] : m[j][i]);
			}
		}
		return arr[less - 1];
	}

}
